package com.leetcode.根据数据结构分类.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/1/5
 * @description: 830. 较大分组的位置
 * https://leetcode-cn.com/problems/positions-of-large-groups/
 * 来自 leetcode 的每日一题
 */
public class A_830_较大分组的位置 {

    /**
     * O(n) 的时间复杂度
     * @param s
     * @return
     */
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> result = new ArrayList<>();
        if (s.length() < 3) {
            return result;
        }
        char[] chars = s.toCharArray();
        //记录分组的值
        char value = chars[0];
        int count = 1;
        //int end = 0;
        for (int i = 1; i < chars.length; i++) {


            if (chars[i] == value) {
                //cout++;

                if (++count > 2) {
                    i++;
                    //追加
                    while (i < chars.length && chars[i] == value) {
                        count++;
                        i++;
                    }

                    //此时已经遍历到底 | 找到相异数据
                    ArrayList<Integer> tempList = new ArrayList<>();
                    tempList.add(i - count);
                    tempList.add(i - 1);
                    result.add(tempList);

                    if (i < chars.length) {
                        value = chars[i];
                        count = 1;
                    }
                }

//                while (++count > 2) {
//                    //当已经统计到三个相同数值时
//                    if (chars[i++] == value) {
//                        count++;
//                    } else {
//                        end = i - 1;
//
//                        ArrayList<Integer> tempList = new ArrayList<>();
//                        tempList.add(end - count);
//                        tempList.add(end - 1);
//                        result.add(tempList);
//
//                        //add new list
//                        value = chars[i];
//                        count = 1;
//                        break;
//                    }
//                }

            } else {
                value = chars[i];
                count = 1;
            }


        }
        return result;
    }

    public static void main(String[] args) {
        final A_830_较大分组的位置 action = new A_830_较大分组的位置();
        String s = "abcdddeeeeaabbbcd";
        //s = "aaa";
        final List<List<Integer>> lists = action.largeGroupPositions(s);
        System.out.println("lists = " + lists);
    }
}
